package com.cty.ThirtiethDay;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/*
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，
满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
* */
public class Q_49 {

    // 力扣官方题解 方法一:递归
    /*
     * 思路:
     *   传入当前节点 让当前节点
     *   是否含有左节点或者右节点
     *   含有 返回true 没有返回
     *   false或者 当前节点为p
     *   或者 q节点 则判断有没
     *   有另一个节点存在其子树
     *   上
     *   时间复杂度O(n) 空间复杂度O(n)
     * */

    private TreeNode ans = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        return ans;
    }

    // 两个节点 只会在同一个父节点的左右字树 或者一方为父节点一方为子节点上
    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean l = dfs(root.left, p, q);
        boolean r = dfs(root.right, p, q);
        if ((l && r) || ((root.val == p.val || root.val == q.val) && (l || r))) {
            ans = root;
        }
        return l || r || (root.val == p.val || root.val == q.val);
    }

    // 力扣官方题解 方法二: 记录父节点
    /*
    * 思路:
    *   用一个哈希表记录每个节点的父节点
    *   我们只需要往上面的节点找 找到第
    *   一个被访问过的即可
    *   时间复杂度O(n) 空间复杂度O(n)
    * */
    // 记录父节点
    Map<Integer,TreeNode> parent = new HashMap<>();
    // 记录被访问过的节点
    Set<TreeNode> visited = new HashSet();
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        // 将节点存入哈希表中
        dfs(root);
        // 访问p节点的父节点并记录被访问的节点
        while (p != null) {
            visited.add(p);
            p = parent.get(p.val);
        }
        // 访问q节点的父节点 返回第一个节点
        while (q != null) {
            if (visited.contains(q)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }

    // 记录父节点
    public void dfs(TreeNode root) {
        if (root == null) return;
        if (root.left != null) {
            parent.put(root.left.val,root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }
}


